PittsburghV1, France, Analysis, bibRecord, 000196

Pay few, influence most: Online myopic network covering

Identifieur interne : 000196 ( France/Analysis ); précédent : 000195; suivant : 000197

Pay few, influence most: Online myopic network covering

Auteurs : Konstantin Avrachenkov [France] ; Prithwish Basu [États-Unis] ; Giovanni Neglia [France] ; Bruno Ribeiro [États-Unis] ; Don Towsley [États-Unis]

Source :

RBID : Hal:hal-01092416

English descriptors

mix :
- greedy algorithms, marketing, social networking (online).

Abstract

Efficient marketing or awareness-raising campaigns seek to recruit a small number, w, of influential individuals - where w is the campaign budget - that are able to cover the largest possible target audience through their social connections. In this paper we assume that the topology is gradually discovered thanks to recruited individuals disclosing their social connections. We analyze the performance of a variety of online myopic algorithms (i.e. that do not have a priori information on the topology) currently used to sample and search large networks. We also propose a new greedy online algorithm, Maximum Expected Uncovered Degree (MEUD). Our proposed algorithm greedily maximizes the expected size of the cover, but it requires the degree distribution to be known. For a class of random power law networks we show that MEUD simplifies into a straightforward procedure, denoted as MOD because it requires only the knowledge of the Maximum Observed Degree.

Url:

https://hal.inria.fr/hal-01092416

DOI: 10.1109/INFCOMW.2014.6849335

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000456
to stream Hal, to step Curation: 000456
to stream Hal, to step Checkpoint: 000221
to stream Main, to step Merge: 000711
to stream Main, to step Curation: 000711
to stream Main, to step Exploration: 000711
to stream France, to step Extraction: 000196

Links to Exploration step

Hal:hal-01092416

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Pay few, influence most: Online myopic network covering</title>
<author><name sortKey="Avrachenkov, Konstantin" sort="Avrachenkov, Konstantin" uniqKey="Avrachenkov K" first="Konstantin" last="Avrachenkov">Konstantin Avrachenkov</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2465" status="VALID">          <idno type="RNSR">200318392H</idno>
          <orgName>Models for the performance analysis and the control of networks</orgName>
          <orgName type="acronym">MAESTRO</orgName>
          <date type="start">2003-10-01</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/maestro</ref>
          </desc>
          <listRelation>            <relation active="#struct-34586" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID">          <idno type="RNSR">198318250R</idno>
          <orgName>Inria Sophia Antipolis - Méditerranée </orgName>
          <orgName type="acronym">CRISAM</orgName>
          <desc>            <address>              <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/sophia/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Basu, Prithwish" sort="Basu, Prithwish" uniqKey="Basu P" first="Prithwish" last="Basu">Prithwish Basu</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-119348" status="VALID">          <orgName>Raytheon BBN Technologies</orgName>
          <desc>            <address>              <addrLine>BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.bbn.com/</ref>
          </desc>
          <listRelation>            <relation active="#struct-312113" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-312113" type="direct"><org type="institution" xml:id="struct-312113" status="INCOMING">          <orgName>BBN Technologies</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Neglia, Giovanni" sort="Neglia, Giovanni" uniqKey="Neglia G" first="Giovanni" last="Neglia">Giovanni Neglia</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2465" status="VALID">          <idno type="RNSR">200318392H</idno>
          <orgName>Models for the performance analysis and the control of networks</orgName>
          <orgName type="acronym">MAESTRO</orgName>
          <date type="start">2003-10-01</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/maestro</ref>
          </desc>
          <listRelation>            <relation active="#struct-34586" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID">          <idno type="RNSR">198318250R</idno>
          <orgName>Inria Sophia Antipolis - Méditerranée </orgName>
          <orgName type="acronym">CRISAM</orgName>
          <desc>            <address>              <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/sophia/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Ribeiro, Bruno" sort="Ribeiro, Bruno" uniqKey="Ribeiro B" first="Bruno" last="Ribeiro">Bruno Ribeiro</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Towsley, Don" sort="Towsley, Don" uniqKey="Towsley D" first="Don" last="Towsley">Don Towsley</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82432" status="VALID">          <orgName>Department of Computer Science [Amherst]</orgName>
          <desc>            <address>              <addrLine>Computer Science Building 140 Governors Drive University of Massachusetts Amherst, MA 01003-9264</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.umass.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-366239" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-366239" type="direct"><org type="institution" xml:id="struct-366239" status="INCOMING">          <orgName>University of Massachusetts</orgName>
          <desc>            <address>              <country key="US"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Amherst (Massachusetts)</settlement>
<region type="state">Massachusetts</region>
</placeName>
<orgName type="university">Université du Massachusetts</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01092416</idno>
<idno type="halId">hal-01092416</idno>
<idno type="halUri">https://hal.inria.fr/hal-01092416</idno>
<idno type="url">https://hal.inria.fr/hal-01092416</idno>
<idno type="doi">10.1109/INFCOMW.2014.6849335</idno>
<date when="2014-05-02">2014-05-02</date>
<idno type="wicri:Area/Hal/Corpus">000456</idno>
<idno type="wicri:Area/Hal/Curation">000456</idno>
<idno type="wicri:Area/Hal/Checkpoint">000221</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000221</idno>
<idno type="wicri:Area/Main/Merge">000711</idno>
<idno type="wicri:Area/Main/Curation">000711</idno>
<idno type="wicri:Area/Main/Exploration">000711</idno>
<idno type="wicri:Area/France/Extraction">000196</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Pay few, influence most: Online myopic network covering</title>
<author><name sortKey="Avrachenkov, Konstantin" sort="Avrachenkov, Konstantin" uniqKey="Avrachenkov K" first="Konstantin" last="Avrachenkov">Konstantin Avrachenkov</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2465" status="VALID">          <idno type="RNSR">200318392H</idno>
          <orgName>Models for the performance analysis and the control of networks</orgName>
          <orgName type="acronym">MAESTRO</orgName>
          <date type="start">2003-10-01</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/maestro</ref>
          </desc>
          <listRelation>            <relation active="#struct-34586" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID">          <idno type="RNSR">198318250R</idno>
          <orgName>Inria Sophia Antipolis - Méditerranée </orgName>
          <orgName type="acronym">CRISAM</orgName>
          <desc>            <address>              <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/sophia/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Basu, Prithwish" sort="Basu, Prithwish" uniqKey="Basu P" first="Prithwish" last="Basu">Prithwish Basu</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-119348" status="VALID">          <orgName>Raytheon BBN Technologies</orgName>
          <desc>            <address>              <addrLine>BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.bbn.com/</ref>
          </desc>
          <listRelation>            <relation active="#struct-312113" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-312113" type="direct"><org type="institution" xml:id="struct-312113" status="INCOMING">          <orgName>BBN Technologies</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Neglia, Giovanni" sort="Neglia, Giovanni" uniqKey="Neglia G" first="Giovanni" last="Neglia">Giovanni Neglia</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2465" status="VALID">          <idno type="RNSR">200318392H</idno>
          <orgName>Models for the performance analysis and the control of networks</orgName>
          <orgName type="acronym">MAESTRO</orgName>
          <date type="start">2003-10-01</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/maestro</ref>
          </desc>
          <listRelation>            <relation active="#struct-34586" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID">          <idno type="RNSR">198318250R</idno>
          <orgName>Inria Sophia Antipolis - Méditerranée </orgName>
          <orgName type="acronym">CRISAM</orgName>
          <desc>            <address>              <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/sophia/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Ribeiro, Bruno" sort="Ribeiro, Bruno" uniqKey="Ribeiro B" first="Bruno" last="Ribeiro">Bruno Ribeiro</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Towsley, Don" sort="Towsley, Don" uniqKey="Towsley D" first="Don" last="Towsley">Don Towsley</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82432" status="VALID">          <orgName>Department of Computer Science [Amherst]</orgName>
          <desc>            <address>              <addrLine>Computer Science Building 140 Governors Drive University of Massachusetts Amherst, MA 01003-9264</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.umass.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-366239" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-366239" type="direct"><org type="institution" xml:id="struct-366239" status="INCOMING">          <orgName>University of Massachusetts</orgName>
          <desc>            <address>              <country key="US"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Amherst (Massachusetts)</settlement>
<region type="state">Massachusetts</region>
</placeName>
<orgName type="university">Université du Massachusetts</orgName>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1109/INFCOMW.2014.6849335</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>greedy algorithms</term>
<term>marketing</term>
<term>social networking (online)</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Efficient marketing or awareness-raising campaigns seek to recruit a small number, w, of influential individuals - where w is the campaign budget - that are able to cover the largest possible target audience through their social connections. In this paper we assume that the topology is gradually discovered thanks to recruited individuals disclosing their social connections. We analyze the performance of a variety of online myopic algorithms (i.e. that do not have a priori information on the topology) currently used to sample and search large networks. We also propose a new greedy online algorithm, Maximum Expected Uncovered Degree (MEUD). Our proposed algorithm greedily maximizes the expected size of the cover, but it requires the degree distribution to be known. For a class of random power law networks we show that MEUD simplifies into a straightforward procedure, denoted as MOD because it requires only the knowledge of the Maximum Observed Degree.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Massachusetts</li>
<li>Pennsylvanie</li>
</region>
<settlement><li>Amherst (Massachusetts)</li>
<li>Pittsburgh</li>
</settlement>
<orgName><li>Université de Pittsburgh</li>
<li>Université du Massachusetts</li>
</orgName>
</list>
<tree><country name="France"><noRegion><name sortKey="Avrachenkov, Konstantin" sort="Avrachenkov, Konstantin" uniqKey="Avrachenkov K" first="Konstantin" last="Avrachenkov">Konstantin Avrachenkov</name>
</noRegion>
<name sortKey="Neglia, Giovanni" sort="Neglia, Giovanni" uniqKey="Neglia G" first="Giovanni" last="Neglia">Giovanni Neglia</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Basu, Prithwish" sort="Basu, Prithwish" uniqKey="Basu P" first="Prithwish" last="Basu">Prithwish Basu</name>
</noRegion>
<name sortKey="Ribeiro, Bruno" sort="Ribeiro, Bruno" uniqKey="Ribeiro B" first="Bruno" last="Ribeiro">Bruno Ribeiro</name>
<name sortKey="Towsley, Don" sort="Towsley, Don" uniqKey="Towsley D" first="Don" last="Towsley">Don Towsley</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000196 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000196 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-01092416
   |texte=   Pay few, influence most: Online myopic network covering
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Pay few, influence most: Online myopic network covering

Pay few, influence most: Online myopic network covering

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri